1083A - The Fair Nut and the Best Path - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
// Define here .
const int N = 3e5+10;
vector<pair <int,ll > > adj[N];
ll w[N],dp[N][2];
int n;
ll D=0;
void dfs(int u,int p)
{
    dp[u][0]=dp[u][1]=w[u];
    for(auto v:adj[u])
    {
        if(v.F==p)
            continue;
        dfs(v.F,u);
        dp[u][1]=max(dp[u][1],dp[v.F][0]+dp[u][0]-v.S);
        dp[u][0]=max(dp[u][0],dp[v.F][0]+w[u]-v.S);
    }
    D =max(D,max(dp[u][0],dp[u][1]));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<n;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].pb({y,w});
        adj[y].pb({x,w});
    }
    dfs(1,-1);
    cout<<D;
    return 0;
}